package beusoft.ccjk.com.calculator.tree;

import java.util.Random;

/**
 * Created by CCJK on 2017/12/21.
 */

public class Tree {


    private static void println(Object o) {
        System.out.println(o);
    }

    private static void print(Object o) {
        System.out.print(" " + o);
    }

    private static void printArr(int arr[]) {
        print("[");
        for (int i = 0; i < arr.length; i++) {
            if (i == arr.length - 1) {
                print(arr[i]);
            } else {
                print(arr[i] + " , ");
            }

        }
        print("]");
    }

    public static void main(String... args) {
        Tree tree = new Tree();
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            tree.insert(new Node(random.nextInt(100)));
        }
        tree.foreach(tree.root);
        Node node = tree.find(50);
        if (node == null) {
            println("not found 50");
        } else {
            println("founded 50");
        }
    }

    private Node root;

    public Tree() {
    }

    public void foreach(Node node) {
        if (node != null) {
            foreach(node.leftNode);
            print(" " + node.key);
            foreach(node.rightNode);
        }
    }


    public void delete(Node node){
        


    }

    public Node find(int key) {
        Node current = root;
        while (current != null) {
            if (current.key < key) {
                current = current.rightNode;
            } else if (current.key > key) {
                current = current.leftNode;
            } else {
                return current;
            }
        }
        return null;
    }

    public void insert(Node node) {
        if (root == null) {
            root = node;
            return;
        }
        Node current = root;
        while (true) {
            if (node.key < current.key) {
                if (current.leftNode == null) {
                    current.leftNode = node;
                    return;
                } else {
                    current = current.leftNode;
                }
            } else {
                if (current.rightNode == null) {
                    current.rightNode = node;
                    return;
                } else {
                    current = current.rightNode;
                }
            }
        }
    }
}
